#include <bits/stdc++.h>

using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

void printf_list(ListNode *head)
{
    ListNode *cur = head;
    while (cur != nullptr)
    {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

class Solution
{
public:
    // ListNode *swapPairs(ListNode *head)
    // {
    //     if (head == nullptr)
    //     {
    //         return head;
    //     }
    //     ListNode *cur = head;
    //     while (cur != nullptr && cur->next != nullptr)
    //     {
    //         int temp = cur->val;
    //         cur->val = cur->next->val;
    //         cur->next->val = temp;
    //         cur = cur->next->next;
    //     }
    //     return head;
    // }

    ListNode *swapPairs(ListNode *head)
    {
        ListNode *dummy_head = new ListNode(0);
        dummy_head->next = head;
        ListNode *cur = dummy_head;
        while (cur->next != nullptr && cur->next->next != nullptr)
        {
            ListNode *tmp1 = cur->next;
            ListNode *tmp2 = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = tmp1;
            cur->next->next->next = tmp2;

            cur = cur->next->next;
        }
        ListNode *res = dummy_head->next;
        delete dummy_head;
        dummy_head = nullptr;
        return res;
    }
};

int main()
{
    ListNode *head = new ListNode(1);
    ListNode *node1 = new ListNode(2);
    ListNode *node2 = new ListNode(3);
    ListNode *node3 = new ListNode(4);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;

    printf_list(head);

    Solution sol;
    ListNode *swap_head = sol.swapPairs(head);

    printf_list(swap_head);

    return 0;
}